/*
 * @lc app=leetcode.cn id=2850 lang=golang
 *
 * [2850] 将石头分散到网格图的最少移动次数
 */
package Solutions

// @lc code=start
func minimumMoves(grid [][]int) int {
	full := make([][]int, 0, 9)
	empty := make([]int, 0, 4)
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if grid[i][j] > 1 {
				full = append(full, []int{i*10 + j, grid[i][j] - 1})
			} else if grid[i][j] == 0 {
				empty = append(empty, i*10+j)
			}
		}
	}
	var dfs func(i int) int
	dfs = func(ii int) int {
		if ii >= len(empty) {
			return 0
		}
		min := 999
		for i := 0; i < len(full); i++ {
			if full[i][1] > 0 {
				p := getDistance(empty[ii], full[i][0])
				full[i][1] -= 1
				p += dfs(ii + 1)
				if p < min {
					min = p
				}
				full[i][1] += 1
			}
		}
		return min
	}
	return dfs(0)

}

func getDistance(p1 int, p2 int) int {
	x1 := p1 / 10
	y1 := p1 % 10
	x2 := p2 / 10
	y2 := p2 % 10
	x1 -= x2
	y1 -= y2
	if x1 < 0 {
		x1 = -x1
	}
	if y1 < 0 {
		x1 -= y1
	} else {
		x1 += y1
	}
	return x1
}

// @lc code=end
